// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，  其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
typedef char DataType;

typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/
#define OK 0
#define ERRO 1
int _create_tree(BiTreeNode **root_pp,char * pre_order_seq,int *current_index){
    int status_sub_tree;
    if(pre_order_seq[*current_index] == '\0'){
        //TODO
        (*root_pp) = NULL;
        return OK;
    }
    if(pre_order_seq[*current_index] == '#'){
        *root_pp = NULL;
        //需要消耗掉这个#字符，因此*current-indez 需要+1
        *current_index += 1;
        return OK;
    }
    (*root_pp)= (BiTreeNode*)malloc(sizeof(BiTreeNode));
    if(!(*root_pp)){
        printf("failed to allocate memory,now exit()");
        return ERRO;
    }
    (*root_pp)->data = pre_order_seq[*current_index];
    *current_index += 1;
    status_sub_tree = _create_tree(&((*root_pp)->leftChild),pre_order_seq, current_index);
    if(status_sub_tree == ERRO){
        return status_sub_tree;
    }
    status_sub_tree = _create_tree(&((*root_pp))->rightChild,pre_order_seq,current_index);
    if(status_sub_tree == ERRO){
        return status_sub_tree;
    }
    return OK;
}
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq,int num_elements) {
    int num_scanned_chars=0;
    _create_tree(root_pp, pre_order_seq,&num_scanned_chars);
    num_elements = num_elements;
    //	num_scanned_chars num_elements
}
//使用visit(item)函数前序来遍历二叉树t
void pre_order_traverse(BiTreeNode *t,void visit(DataType item)){
    if(t == NULL){
        return ;
    }
    visit (t->data);
    pre_order_traverse(t->leftChild, visit);
    pre_order_traverse(t->rightChild, visit);
}
//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if(t == NULL){
        return ;
    }
    in_order_traverse(t->leftChild, visit);
    visit (t->data);
    in_order_traverse(t->rightChild, visit);
}
//使用visit(item)函数后序序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t == NULL){
        return ;
    }
    post_order_traverse(t->leftChild, visit);
    post_order_traverse(t->rightChild, visit);
    visit (t->data);


}
// 可以无需更改本函数的实现
void visit(DataType item)
{
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)
{
    BiTreeNode *find;
    //空树找不到
    if (root == NULL)
        return NULL;
    if (root->data == x)  // 找到了返回 root
        return root;
    //查找左右子树
    find = search(root->leftChild, x);
    if (find)  //不为空就继续查找
        return find;
    return search(root->rightChild, x);

}
// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
    BiTreeNode* cur = *root;
    if (cur) {
        destroy(&cur->leftChild);
        destroy(&cur->rightChild);
        free(cur);
        *root = NULL;
    }

}
int main() {

    BiTreeNode* root_pp;
    create_tree(&root_pp,"ABC##DE#G##F###", 21 );
    pre_order_traverse(root_pp, visit);
    in_order_traverse(root_pp,  visit);
    post_order_traverse(root_pp, visit);





}